package _剑指offer.二叉树;

import util.TreeNode;
import org.junit.Test;

public class _68_1_二叉搜索树的最近公共祖先 {
    @Test
    public void main() {
        Integer[] input = new Integer[]{6,2,8,0,4,7,9,null,null,3,5};
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println("ancestor = " + lowestCommonAncestor(root, new TreeNode(2), new TreeNode(8)).val);
    }
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }
}
